package bintree.leetcode;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2022/9/29 14:40
 * @Description:寻找重复子树
 */
public class Num652_FindDuplicateSubtrees {
    /**
     * 解决这个问题需要知道两点:
     * 1.以我为根的子树长啥样?
     * 2.别人的子树长啥样？
     * 解决第一个问题其实就是序列化
     * 解决第二个问题只需要将每个子树遍历结果存储在外部数据结构即可。
     * 每当遍历完一个子树，将序列化结果以及出现次数存储到Map中
     * @param root
     * @return
     */
    // 存储每个子树以及出现次数
    private Map<String,Integer> subTrees = new HashMap<>();
    // 存储结果集
    private List<TreeNode> res = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    /**
     * 序列化以当前root为根的二叉树
     * @param root
     * @return
     */
    private String traverse(TreeNode root) {
        // base case
        if (root == null) {
            return "#";
        }
        // 左树和右树的序列化结果
        String left = traverse(root.left);
        String right = traverse(root.right);
        // 当前树的后序序列序列化结果
        String cur = left + "," + right + "," + root.val;
        // 当前子树在所有树中的出现次数，若第一次出现，则为0
        int freq = subTrees.getOrDefault(cur,0);
        if (freq == 1) {
            // 当前树的序列化结果已经在其他位置出现过，结果集添加当前树根
            // 多次出现的重复子树只添加一次,即第一次碰到重复树时添加
            res.add(root);
        }
        subTrees.put(cur,freq + 1);
        return cur;
    }
}
